// 版权所有2009年围棋作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 包rsa实现PKCS#1和RFC 8017中指定的rsa加密。
// None
// RSA是本软件包中用于
// 实现公钥加密或公钥签名。
// None
// RSA加密和签名的原始规范是PKCS#1
// 术语“RSA加密”和“RSA签名”默认指
// PKCS#1 1.5版。然而，该规范存在缺陷和新设计
// 应该使用版本2，通常仅由OAEP和PSS调用，其中
// 可能的
// None
// 此包中包含两组接口。当一个更抽象的
// 接口不是必需的，有用于加密/解密的函数
// 使用v1.5/OAEP，并使用v1.5/PSS进行签名/验证。如果需要抽象
// 在公钥原语上，PrivateKey类型实现
// 加密包中的解密程序和签名程序接口。
// None
// 此包中的RSA操作不是使用恒定时间算法实现的。
package rsa

import (
	"crypto"
	"crypto/rand"
	"crypto/subtle"
	"errors"
	"hash"
	"io"
	"math"
	"math/big"

	"crypto/internal/randutil"
)

var bigZero = big.NewInt(0)
var bigOne = big.NewInt(1)

// 公钥表示RSA密钥的公共部分。
type PublicKey struct {
	N *big.Int // 模数
	E int      // 公开指数
}

// 在公钥上实现的任何方法可能也需要在公钥上实现
// PrivateKey，后者嵌入前者并公开其方法。

// Size返回以字节为单位的模数大小。原始签名和密文
// 对于或通过此公钥将具有相同的大小。
func (pub *PublicKey) Size() int {
	return (pub.N.BitLen() + 7) / 8
}

// Equal报告pub和x是否具有相同的值。
func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
	xx, ok := x.(*PublicKey)
	if !ok {
		return false
	}
	return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E
}

// OAEPOptions是一个接口，用于使用
// 加密解密接口。
type OAEPOptions struct {
	// 哈希是生成掩码时将使用的哈希函数。
	Hash crypto.Hash
	// Label是一个任意字节字符串，必须等于该值
	// 加密时使用。
	Label []byte
}

var (
	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
)

// checkPub sanity在使用公钥之前检查公钥。
// 我们要求pub.E适合32位整数，以便
// 没有不同的行为取决于是否
// int是32或64位。另见
// https:
func checkPub(pub *PublicKey) error {
	if pub.N == nil {
		return errPublicModulus
	}
	if pub.E < 2 {
		return errPublicExponentSmall
	}
	if pub.E > 1<<31-1 {
		return errPublicExponentLarge
	}
	return nil
}

// PrivateKey表示RSA密钥
type PrivateKey struct {
	PublicKey            // 公共部分。
	D         *big.Int   // 私人指数
	Primes    []*big.Int // N的素因子，有>=2个元素。

	// 预计算包含预计算值，这些值可以加速私有
	// 操作，如果可用。
	Precomputed PrecomputedValues
}

// Public返回与priv相对应的公钥。
func (priv *PrivateKey) Public() crypto.PublicKey {
	return &priv.PublicKey
}

// Equal报告priv和x是否具有等效值。它忽略了
// 预计算值。
func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
	xx, ok := x.(*PrivateKey)
	if !ok {
		return false
	}
	if !priv.PublicKey.Equal(&xx.PublicKey) || priv.D.Cmp(xx.D) != 0 {
		return false
	}
	if len(priv.Primes) != len(xx.Primes) {
		return false
	}
	for i := range priv.Primes {
		if priv.Primes[i].Cmp(xx.Primes[i]) != 0 {
			return false
		}
	}
	return true
}

// 与priv签署摘要，阅读兰德公司的随机性。如果opts是一个
// *PSS选项然后将使用PSS算法，否则将使用PKCS#1 v1.5
// 被使用。摘要必须是使用
// opts.HashFunc（）。
// None
// 此方法实现crypto.Signer，这是一个支持密钥的接口
// 其中私有部分保存在例如硬件模块中。常见的
// 用户应直接使用此包中的Sign*函数。
func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
	if pssOpts, ok := opts.(*PSSOptions); ok {
		return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
	}

	return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
}

// Decrypt使用priv解密密文。如果opts为nil或类型为
// *PKCS1v15DecryptOptions然后执行PKCS#1V1.5解密。否则
// OPT必须具有类型*OAEPOptions，并且OAEP解密已完成。
func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
	if opts == nil {
		return DecryptPKCS1v15(rand, priv, ciphertext)
	}

	switch opts := opts.(type) {
	case *OAEPOptions:
		return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)

	case *PKCS1v15DecryptOptions:
		if l := opts.SessionKeyLen; l > 0 {
			plaintext = make([]byte, l)
			if _, err := io.ReadFull(rand, plaintext); err != nil {
				return nil, err
			}
			if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
				return nil, err
			}
			return plaintext, nil
		} else {
			return DecryptPKCS1v15(rand, priv, ciphertext)
		}

	default:
		return nil, errors.New("crypto/rsa: invalid options for Decrypt")
	}
}

type PrecomputedValues struct {
	Dp, Dq *big.Int // D型（P-1）（或Q-1型）
	Qinv   *big.Int // Q^-1模P

	// CRT值用于第三个和后续的素数。由于
	// 历史事故，处理前两个素数的CRT
	// PKCS#1中的不同之处在于，互操作性已足够
	// 重要的是，我们要反映这一点。
	CRTValues []CRTValue
}

// CRT值包含预计算的中国剩余定理值。
type CRTValue struct {
	Exp   *big.Int // D模（素数-1）。
	Coeff *big.Int // R·系数≡ 1模素数。
	R     *big.Int // 在此之前的素数乘积（包括p和q）。
}

// Validate对密钥执行基本的健全性检查。
// 如果密钥有效，则返回nil，否则返回描述问题的错误。
func (priv *PrivateKey) Validate() error {
	if err := checkPub(&priv.PublicKey); err != nil {
		return err
	}

	// 检查∏素数==n。
	modulus := new(big.Int).Set(bigOne)
	for _, prime := range priv.Primes {
		// 有素数吗≤ 1将导致随后的除以零恐慌。
		if prime.Cmp(bigOne) <= 0 {
			return errors.New("crypto/rsa: invalid prime value")
		}
		modulus.Mul(modulus, prime)
	}
	if modulus.Cmp(priv.N) != 0 {
		return errors.New("crypto/rsa: invalid modulus")
	}

	// 检查一下≡ 1个模块p-1，用于每个素数。
	// 这意味着e是每个p-1的互质，因为e有一个乘法
	// 相反的因此e是lcm的互质（p-1，q-1，r-1，…）=
	// None
	// 国防部。因此^德≡ 根据需要，一个mod n表示所有a到n的互质。
	congruence := new(big.Int)
	de := new(big.Int).SetInt64(int64(priv.E))
	de.Mul(de, priv.D)
	for _, prime := range priv.Primes {
		pminus1 := new(big.Int).Sub(prime, bigOne)
		congruence.Mod(de, pminus1)
		if congruence.Cmp(bigOne) != 0 {
			return errors.New("crypto/rsa: invalid exponents")
		}
	}
	return nil
}

// GenerateKey使用
// 随机源随机（例如，crypto/rand.Reader）。
func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
	return GenerateMultiPrimeKey(random, 2, bits)
}

// GenerateMultiPrimeKey生成给定位的多素数RSA密钥对
// 尺寸和给定的随机源，如[1]所示。虽然公众
// 键与2-素数的情况兼容（实际上无法区分），
// 私钥不可用。因此，可能无法导出多素数
// 某些格式的私钥或随后将其导入其他格式的私钥
// 密码
// None
// [2]中的表1给出了给定大小的最大素数。
// None
// [1] 美国专利4405829（1972年，过期）
// [2] http:
func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
	randutil.MaybeReadByte(random)

	priv := new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	if bits < 64 {
		primeLimit := float64(uint64(1) << uint(bits/nprimes))
		// pi近似于小于primeLimit的素数
		pi := primeLimit / (math.Log(primeLimit) - 1)
		// 生成的素数从11开始（二进制），因此我们只能
		// 使用它们的四分之一。
		pi /= 4
		// 使用系数2确保密钥生成终止
		// 在合理的时间内。
		pi /= 2
		if pi <= float64(nprimes) {
			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
		}
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		// crypto/rand应设置每个素数中的前两位。
		// 因此，每个素数都有其形式
		// p_i=2^bitlen（p_i）×0.11。。。（在基数2中）。
		// 该产品是：
		// P=2^todo×α
		// 其中α是形式为0.11的n次数的乘积。。。
		// None
		// 如果α<1/2（n次>2时可能发生），我们需要
		// 移位todo以补偿丢失的位：平均值0.11。。。
		// 是7/8，所以todo+shift-n时间*log2（7/8）~=位-1/2
		// 会有很好的效果。
		if nprimes >= 7 {
			todo += (nprimes - 2) / 5
		}
		for i := 0; i < nprimes; i++ {
			var err error
			primes[i], err = rand.Prime(random, todo/(nprimes-i))
			if err != nil {
				return nil, err
			}
			todo -= primes[i].BitLen()
		}

		// 确保素数成对不相等。
		for i, prime := range primes {
			for j := 0; j < i; j++ {
				if prime.Cmp(primes[j]) == 0 {
					continue NextSetOfPrimes
				}
			}
		}

		n := new(big.Int).Set(bigOne)
		totient := new(big.Int).Set(bigOne)
		pminus1 := new(big.Int)
		for _, prime := range primes {
			n.Mul(n, prime)
			pminus1.Sub(prime, bigOne)
			totient.Mul(totient, pminus1)
		}
		if n.BitLen() != bits {
			// 对于n次==2，这种情况永远不会发生，因为
			// crypto/rand应设置每个素数中的前两位。
			// 我们希望这种情况不会经常发生。
			continue NextSetOfPrimes
		}

		priv.D = new(big.Int)
		e := big.NewInt(int64(priv.E))
		ok := priv.D.ModInverse(e, totient)

		if ok != nil {
			priv.Primes = primes
			priv.N = n
			break
		}
	}

	priv.Precompute()
	return priv, nil
}

// incCounter递增一个四字节的大端计数器。
func incCounter(c *[4]byte) {
	if c[3]++; c[3] != 0 {
		return
	}
	if c[2]++; c[2] != 0 {
		return
	}
	if c[1]++; c[1] != 0 {
		return
	}
	c[0]++
}

// mgf1XOR使用使用MGF1函数生成的掩码对字节进行异或
// 在PKCS#1 v2.1中规定。
func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
	var counter [4]byte
	var digest []byte

	done := 0
	for done < len(out) {
		hash.Write(seed)
		hash.Write(counter[0:4])
		digest = hash.Sum(digest[:0])
		hash.Reset()

		for i := 0; i < len(digest) && done < len(out); i++ {
			out[done] ^= digest[i]
			done++
		}
		incCounter(&counter)
	}
}

// 尝试加密以下消息时返回ErrMessageTooLong
// 对于公钥的大小来说太大。
var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")

func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
	e := big.NewInt(int64(pub.E))
	c.Exp(m, e, pub.N)
	return c
}

// EncryptOAEP使用RSA-OAEP加密给定的消息。
// None
// OAEP由用作随机预言的哈希函数参数化。
// 给定消息的加密和解密必须使用相同的哈希函数
// 而sha256.New（）是一个合理的选择。
// None
// 随机参数用作熵源，以确保
// 对同一消息加密两次不会产生相同的密文。
// None
// label参数可能包含不加密的任意数据，
// 但这为信息提供了重要的背景。例如，如果给定
// 公钥用于加密两种类型的消息，然后使用不同的标签
// 可以使用值来确保不能使用用于某一目的的密文
// 被攻击者用于另一个目的。如果不需要，它可以是空的。
// None
// 消息的长度不能超过公共消息的长度
// 哈希长度的两倍，再减去2。
func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
	if err := checkPub(pub); err != nil {
		return nil, err
	}
	hash.Reset()
	k := pub.Size()
	if len(msg) > k-2*hash.Size()-2 {
		return nil, ErrMessageTooLong
	}

	hash.Write(label)
	lHash := hash.Sum(nil)
	hash.Reset()

	em := make([]byte, k)
	seed := em[1 : 1+hash.Size()]
	db := em[1+hash.Size():]

	copy(db[0:hash.Size()], lHash)
	db[len(db)-len(msg)-1] = 1
	copy(db[len(db)-len(msg):], msg)

	_, err := io.ReadFull(random, seed)
	if err != nil {
		return nil, err
	}

	mgf1XOR(db, hash, seed)
	mgf1XOR(seed, hash, db)

	m := new(big.Int)
	m.SetBytes(em)
	c := encrypt(new(big.Int), pub, m)

	out := make([]byte, k)
	return c.FillBytes(out), nil
}

// ErrDecryption表示解密消息失败。
// 它是故意模糊的，以避免自适应攻击。
var ErrDecryption = errors.New("crypto/rsa: decryption error")

// ErrVerification表示验证签名失败。
// 它是故意模糊的，以避免自适应攻击。
var ErrVerification = errors.New("crypto/rsa: verification error")

// 预计算机执行一些计算以加速私钥操作
// 未来
func (priv *PrivateKey) Precompute() {
	if priv.Precomputed.Dp != nil {
		return
	}

	priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
	priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)

	priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
	priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)

	priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])

	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
	priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
	for i := 2; i < len(priv.Primes); i++ {
		prime := priv.Primes[i]
		values := &priv.Precomputed.CRTValues[i-2]

		values.Exp = new(big.Int).Sub(prime, bigOne)
		values.Exp.Mod(priv.D, values.Exp)

		values.R = new(big.Int).Set(r)
		values.Coeff = new(big.Int).ModInverse(r, prime)

		r.Mul(r, prime)
	}
}

// decrypt执行RSA解密，生成纯文本整数。如果
// 给出了随机源，采用RSA盲法。
func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
	// TODO（agl）：我们可以不用再使用百叶窗吗？
	if c.Cmp(priv.N) > 0 {
		err = ErrDecryption
		return
	}
	if priv.N.Sign() == 0 {
		return nil, ErrDecryption
	}

	var ir *big.Int
	if random != nil {
		randutil.MaybeReadByte(random)

		// 已启用致盲。致盲包括c乘以r^e。
		// 然后解密操作执行（m^e*r^e）^d mod n
		// 这等于莫德先生。然后，可以去除r的因子
		// 通过乘以r的乘法逆。

		var r *big.Int
		ir = new(big.Int)
		for {
			r, err = rand.Int(random, priv.N)
			if err != nil {
				return
			}
			if r.Cmp(bigZero) == 0 {
				r = bigOne
			}
			ok := ir.ModInverse(r, priv.N)
			if ok != nil {
				break
			}
		}
		bigE := big.NewInt(int64(priv.E))
		rpowe := new(big.Int).Exp(r, bigE, priv.N) // N！=0
		cCopy := new(big.Int).Set(c)
		cCopy.Mul(cCopy, rpowe)
		cCopy.Mod(cCopy, priv.N)
		c = cCopy
	}

	if priv.Precomputed.Dp == nil {
		m = new(big.Int).Exp(c, priv.D, priv.N)
	} else {
		// 我们有CRT所需的预计算值。
		m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
		m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
		m.Sub(m, m2)
		if m.Sign() < 0 {
			m.Add(m, priv.Primes[0])
		}
		m.Mul(m, priv.Precomputed.Qinv)
		m.Mod(m, priv.Primes[0])
		m.Mul(m, priv.Primes[1])
		m.Add(m, m2)

		for i, values := range priv.Precomputed.CRTValues {
			prime := priv.Primes[2+i]
			m2.Exp(c, values.Exp, prime)
			m2.Sub(m2, m)
			m2.Mul(m2, values.Coeff)
			m2.Mod(m2, prime)
			if m2.Sign() < 0 {
				m2.Add(m2, prime)
			}
			m2.Mul(m2, values.R)
			m.Add(m, m2)
		}
	}

	if ir != nil {
		// 揭盲。
		m.Mul(m, ir)
		m.Mod(m, priv.N)
	}

	return
}

func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
	m, err = decrypt(random, priv, c)
	if err != nil {
		return nil, err
	}

	// 为了防止CRT计算中的错误，m^e是
	// 已计算，应与原始密文匹配。
	check := encrypt(new(big.Int), &priv.PublicKey, m)
	if c.Cmp(check) != 0 {
		return nil, errors.New("rsa: internal error")
	}
	return m, nil
}

// DecryptOAEP使用RSA-OAEP解密密文。
// None
// OAEP由用作随机预言的哈希函数参数化。
// 给定消息的加密和解密必须使用相同的哈希函数
// 而sha256.New（）是一个合理的选择。
// None
// 随机参数（如果不是nil）用于对私钥操作进行盲操作
// 并避免定时侧通道攻击。致盲纯粹是这一现象的内在原因
// 函数–随机数据不需要与加密时使用的数据匹配。
// None
// label参数必须与加密时给定的值匹配。看见
// 详细信息请参阅。
func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
	if err := checkPub(&priv.PublicKey); err != nil {
		return nil, err
	}
	k := priv.Size()
	if len(ciphertext) > k ||
		k < hash.Size()*2+2 {
		return nil, ErrDecryption
	}

	c := new(big.Int).SetBytes(ciphertext)

	m, err := decrypt(random, priv, c)
	if err != nil {
		return nil, err
	}

	hash.Write(label)
	lHash := hash.Sum(nil)
	hash.Reset()

	// 我们可能泄漏了前导零的数量。
	// 目前还不清楚我们是否能对此采取任何措施。
	em := m.FillBytes(make([]byte, k))

	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)

	seed := em[1 : hash.Size()+1]
	db := em[hash.Size()+1:]

	mgf1XOR(seed, hash, db)
	mgf1XOR(db, hash, seed)

	lHash2 := db[0:hash.Size()]

	// 我们必须在固定时间内验证明文，以避免
	// 攻击像：J.Manger。对RSA最优解的选择密文攻击
	// PKCS#1中标准化的非对称加密填充（OAEP）
	// v2.0。《密码学进展》编辑J.Kilian。
	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)

	// 纯文本的其余部分必须为零或多个0x00，后跟
	// 按0x01，然后是消息。
	// lookingForIndex:1如果我们仍在寻找0x01
	// 索引：第一个0x01字节的偏移量
	// 无效：1如果我们在0x01之前看到一个非零字节。
	var lookingForIndex, index, invalid int
	lookingForIndex = 1
	rest := db[hash.Size():]

	for i := 0; i < len(rest); i++ {
		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
	}

	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
		return nil, ErrDecryption
	}

	return rest[index+1:], nil
}
